package week_01;

public class ReverseKLinkNode {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode protect = new ListNode(-1);
        ListNode nextHead = null;
        ListNode lastTail = protect;

        while (head != null) {
            ListNode end = getEndNode(head, k);
            if (end == null) {
                break;
            }
            nextHead = end.next;
            reverseList(head, end);
            lastTail.next = end;
            head.next = nextHead;
            lastTail=head;
            head = nextHead;
        }
        return protect.next;
    }

    public static ListNode getEndNode(ListNode head, int k) {
        if (head.next == null) return head;
        while (k > 1 && head != null) {
            head = head.next;
            k--;
        }
        return head;
    }

    public static void reverseList(ListNode head, ListNode end) {
        if(head==end) return;
        ListNode last = head;
        head=head.next;
        while (head != end) {
            ListNode nextTmp = head.next;
            head.next = last;
            last = head;
            head = nextTmp;
        }
        end.next=last;
    }

    public static void main(String[] args) {

        ListNode head = new ListNode(-1);
        ListNode root =head;
        int[] arr = new int[]{1, 2, 3, 4, 5};
        for(int i=0;i<arr.length;i++){
            ListNode tmp =new ListNode(arr[i]);
            head.next=tmp;
            head=tmp;
        }
        reverseKGroup(root.next,2);
    }
}




